## python 3.9.13
#%%
import random

#%%[markdown]
""" 
#### 编程实现二叉排序树，包括
1. 插入结点，删除结点； 
2. 对二叉排序树进行前序、中序、和后序非递归遍历;
3. 查找某个结点是否存在，如果能找到在屏幕上打印存在结点，否则打印不存
"""
#%%


class Stack(object):
    """ 
    栈操作类
    """
    def __init__(self):
        self.__data = []
        self.Size = 0 # 用于判断数据是否位空

    def push(self, data):
        self.Size += 1
        self.__data = [data] + self.__data

    def pull(self):
        tmp = self.__data[0]
        self.__data = self.__data[1:]
        self.Size -= 1
        return tmp

    def getTop(self):
        return self.__data[0] if self.Size > 0 else None

    def Distory(self):
        self.__data = []
        self.Size = 0
        del self.__data, self.Size


class Queue(Stack):
    """ 
    队列操作类
    """
    def __init__(self):
        super(Queue, self).__init__()
        self.__data = []

    def push(self, data):
        self.Size += 1
        self.__data = self.__data + [data]

    def pull(self):
        self.Size -= 1
        tmp = self.__data[0]
        self.__data = self.__data[1:]
        return tmp


class BinTreeNode(object):
    """ 
    创建树节点
    """
    data = None
    counts = 0 # 由于构建的为二叉搜索树,为了确保节点唯一性,则再节点处进行计数处理.
    LChild, RChild = None, None # 左节点,右节点


class BinaryTree(object):
    def __init__(self):
        self.Tree = None
        
    def addTreeNode(self, Data):
        """ 
        为树添加节点
        + Data::需要添加入节点的参数
        """
        treeNode = BinTreeNode() # 初始化节点
        treeNode.data = Data # 节点赋值
        if self.Tree: # 如果树存在
            cursor = self.__SearchNode(self.Tree, Data)[0] # 调用节点搜索,取第一个返回值
            treeNode.counts += 1 # 节点中计数+1
            if cursor: # 如果找到游标
                if Data == cursor.data: # 值一致计数+1
                    cursor.counts += 1
                elif cursor.LChild is None and Data < cursor.data: # 如果值小,则再左侧创建节点
                    cursor.LChild = treeNode
                elif cursor.RChild is None and Data > cursor.data: # 如果值大,则再右侧创建节点
                    cursor.RChild = treeNode
        else: # 如果树尚未生成,则初始化树
            self.Tree = treeNode
            self.Tree.counts += 1

    def __SearchNode(self, cursor, Data, NodeInd=1, path="Root->"):
        # 采用私有函数创建
        """
        通过递归方式对节点进行搜索,找到值应该所处的位置.
        + cursor::当前操作指针
        + Data::比对数值
        return:
        + cursor::与值一致的指针
        + NodeInd::指针所有值
        + path::值所在的路径
        """
        if cursor:
            if (
                cursor.data == Data
                or (cursor.LChild is None and Data < cursor.data)
                or cursor.RChild is None and Data > cursor.data
            ):
                #1. 如果数据一致,则代表找到节点,
                #2. 如果数据不一致,且其后节点为空,则代表节点尚未创建.
                # 不论如何都会返回一个节点,也可能是空节点
                stats = None 
                if cursor.data == Data:
                    stats = True # 确定值状态,用于后续搜索函数
                return cursor, NodeInd, path[:-2], stats
            elif cursor.LChild and Data < cursor.data:
                NodeInd *= 2
                path += "L->"
                return self.__SearchNode(cursor.LChild, Data, NodeInd, path)
            elif cursor.RChild and Data > cursor.data:
                NodeInd = NodeInd * 2 + 1
                path += "R->"
                return self.__SearchNode(cursor.RChild, Data, NodeInd, path)

    def Search(self, Data):
        """ 
        搜索函数
        + Data::需要搜索的值
        """
        cursor, index, SearchPath, SearchStats = self.__SearchNode(self.Tree, Data)
        if SearchStats: # 如果值被找到,则返回
            return cursor.data, index, SearchPath
        else: # 否则返回未找到
            return "未能找到节点", None, None

    def __GetParentsNode(self, Data):
        """ 
        通过循环方式,搜索父节点,并且返回父节点和目标值所处分支
        + Data::目标值
        """
        cursor = self.Tree
        while True:
            if cursor:
                if cursor.LChild is None and cursor.RChild is None:
                    # 搜索到最后叶子节点,依然没有找到,则返回空空
                    # 后续函数中怼空空进行失败处理
                    return None, None
                elif cursor.LChild and cursor.LChild.data == Data:
                    # 搜索到,返回父节点和位置信息
                    return cursor, "LC"
                elif cursor.RChild and cursor.RChild.data == Data:
                    return cursor, "RC"
                elif cursor.data == Data: # 根节点需要左特殊处理
                    return cursor, "Root"
                elif Data < cursor.data: # 切换节点
                    cursor = cursor.LChild
                elif Data > cursor.data: # 切换节点
                    cursor = cursor.RChild
            else:
                # 搜索失败,视为双节点空
                return None, None

    def __NodeOp(self, Node, Side, NewNode):
        # 由于需要重复判断,这里建立了一个简单的替换函数
        if Side == "LC":
            Node.LChild = NewNode
        elif Side == "RC":
            Node.RChild = NewNode

    def DropNode(self, Data):
        """
        如果节点为叶子节点(左右均空,则直接将节点改为空)
        + Data::需要从树中被移除的节点值
        """
        ParNode, side = self.__GetParentsNode(Data) # 获取父节点位置
        if ParNode:
            # 为目标值节点建立指针
            if side == "LC":
                currNode = ParNode.LChild
            elif side == "RC":
                currNode = ParNode.RChild
            else:
                currNode = ParNode

            if currNode:
                LC,RC = currNode.LChild, currNode.RChild

                if LC is None and RC is None: # 叶子节点处理
                    self.__NodeOp(ParNode, side, None) # 直接将叶子节点改为空
                    
                elif LC and RC: # 两侧均有值的节点处理
                    # 如果双侧有值,则统一进行先左后右的操作
                    # 将左节点值赋值给右节点左节点后的叶子.
                    if side != "Root": # 如果是根节点需要特殊操作,无需将节点向下移动
                        ParNode_LC = ParNode.LChild # L -> R
                        if ParNode_LC.RChild:
                            ParNode_LC = ParNode_LC.RChild
                    else:
                        ParNode_LC = ParNode.RChild # -> R
                        
                    currNode = currNode.LChild  # 遍历curr的->L节点的后续R节点.
                    while currNode.RChild:
                        currNode = currNode.RChild

                    self.__NodeOp(currNode, "RC", ParNode_LC) # 修改值
                    if side != "Root":
                        # 如果不是根节点,则将父节点的目标值修改为父节点的node->L->L
                        self.__NodeOp(ParNode, "LC", ParNode.LChild.LChild)
                    else:
                        tmp = ParNode.LChild # 由于需要将整个右侧树切掉,建立临时变量
                        self.Tree = tmp # 赋值给树
                elif LC or RC:
                    # 单侧有值的情况,直接将值进行替换处理
                    self.__NodeOp(ParNode, side, LC if LC else RC)
                print(Data, "node Droped,节点已删除")
        else:
            print("Node Not Found 未能找到目标节点")
            
    def NLR_FrontOrder_recurc(self):
        """ 
        前序遍历,递归版本
        """
        print("_NLR Frist Order->",end=' ')
        cursor = self.Tree # 创建指针
        self.__NLR_FrontOrder_recurc(cursor) # 调用方法
        print()

    def __NLR_FrontOrder_recurc(self, cursor, level=1, order=1):
        """ 
        递归方式建立前序遍历
        + cursor::需要递归的指针
        + Level::当前层
        + order::当前索引
        """
        if cursor:
            print(cursor.data ,# level, order,
                  end=" ")
            return self.__NLR_FrontOrder_recurc(
                cursor.LChild, level + 1, order * 2
            ), self.__NLR_FrontOrder_recurc(
                cursor.RChild, level + 1, order * 2 + 1
            )
        else:
            return

    def NLR_FrontOrder(self):
        """
        前序遍历,单循环版本
        """
        stack = Stack()
        cursor = self.Tree
        refList = [] # 建立一个参考容器,用于存储已经遍历过的节点
        print(" NLR Frist Order", end="-> ")
        while True:
            if cursor:
                if cursor not in refList: # 如果参考容器中不包含内容
                    print(cursor.data, end=" ") # 输出数值
                    refList.append(cursor) # 添加到容器中
                    stack.push(cursor) # 由表入栈
                    if cursor.LChild: # 判断是否包含左树
                        cursor = cursor.LChild
                elif cursor.RChild: # 如果节点再容器中已经存在,则判断是否包含右树
                    cursor = cursor.RChild
                elif stack.Size > 0: # 如果栈未空
                    cursor = stack.pull() 
                else:
                    break # 中断循环
            elif stack.Size == 0: # 如果栈空.中断循环
                break
        print()

    def NLR_FrontOrder_Cpp(self):
        """
        前序遍历,参考CPP中代码
        """
        stack = Stack()
        cursor = self.Tree
        print("*NLR Frist Order", end="-> ")
        while True:
            while cursor: #如果指针不为空(如果到叶子节点则会为空)
                print(cursor.data, end=" ") 
                stack.push(cursor) # 当前指针入栈
                cursor = cursor.LChild # 指针指向节点左侧
            if stack.Size > 0: # 如果栈未空,则从栈顶获取元素,并且指向右节点
                cursor = stack.pull()
                cursor = cursor.RChild
            if cursor is None and stack.Size == 0:
                # 如果指针为空,且栈空,则退出循环
                break
        print() # 接收换行

    def LNR_MiddleOrder_Cpp(self):
        """
        中序遍历,参考Cpp代码
        """
        stack = Stack()
        cursor = self.Tree
        print("*LNR MiddleOrder", end="-> ")
        while True:
            while cursor: # 如果指针不为空(如果到叶子节点则会为空)
                stack.push(cursor) # 当前指针入栈
                cursor = cursor.LChild # 指针指向节点左侧
            if stack.Size != 0: # 如果栈未空,则从栈顶获取元素,打印元素,并且指向右节点
                cursor = stack.pull() 
                print(cursor.data, end=" ")
                cursor = cursor.RChild
            if cursor is None and stack.Size == 0:
                # 如果指针为空,且栈空,则退出循环
                break
        print()

    def LevelOrder_Cpp(self):
        """
        层序遍历,层序遍历,参考Cpp代码
        """
        queue = Queue()
        cursor = self.Tree
        queue.push(cursor)
        print("*    Level Order->", end=" ")
        while queue.Size > 0: # 如果队列不为空
            cursor = queue.pull() # 队列中取一个值
            print(cursor.data, end=" ") # 打印该值
            # 如果存在后续节点,则将节点添加至队列中
            if cursor.LChild:
                queue.push(cursor.LChild)
            if cursor.RChild:
                queue.push(cursor.RChild)
        print()

    def LRN_BackOrder(self):
        """
        后序遍历,视频中双栈版本
        将当前节点入栈后,取栈顶元素,将两个子节点添加到临时栈
        重复上述操作,当临时站被取完后,
        遍历输出站,从栈顶获取元素并打印.
        """
        stackTmp = Stack()  # S1
        stackMain = Stack()  # S2
        cursorMain = self.Tree
        print("=LRN  Last Order->", end=" ")
        stackTmp.push(cursorMain)  # 根节点压入栈
        while stackTmp.Size > 0:
            cursorMain = stackTmp.pull()  # 当前指针为临时栈栈顶元素
            stackMain.push(cursorMain)
            if cursorMain.LChild:
                stackTmp.push(cursorMain.LChild)  # 将栈顶元素左儿子压入输出栈
            if cursorMain.RChild:
                stackTmp.push(cursorMain.RChild)  # 将栈顶元素左儿子压入输出栈
            # 当tmp栈中还有元素,则遍历继续,否则结束
        while stackMain.Size > 0:
            cursorMain = stackMain.pull()
            print(cursorMain.data, end=" ")
        print()


#%%

if __name__ == '__main__':
    newTree = BinaryTree() # 初始化树
    ranDataList = [5, 3, 9, 1, 4, 7, 8, 0, 2, 6, 11, 12, 10, 13, 14, 15] # 指定树类型

    print(set(ranDataList)) # 去重后的节点,输出值应该与中序一致.
    for i in ranDataList:
        newTree.addTreeNode(i)

    #%%
    newTree.NLR_FrontOrder_recurc() # 前序递归
    newTree.NLR_FrontOrder() # 前序单循环
    newTree.NLR_FrontOrder_Cpp() # 前序cpp
    newTree.LNR_MiddleOrder_Cpp() # 中序cpp
    newTree.LevelOrder_Cpp() # 层序测试
    newTree.LRN_BackOrder() # 双栈后续
    #%%

    newTree.LNR_MiddleOrder_Cpp() # 中序遍历
    newTree.DropNode(15) # 删除叶子节点测试
    newTree.LNR_MiddleOrder_Cpp()
    newTree.DropNode(13) # 删除单右侧节点测试
    newTree.LNR_MiddleOrder_Cpp()
    newTree.DropNode(3) # 删除含有双侧的节点测试
    newTree.LNR_MiddleOrder_Cpp()
    newTree.DropNode(1) # 再次删除
    newTree.LNR_MiddleOrder_Cpp()
    newTree.DropNode(5) # 根节点测试
    newTree.LNR_MiddleOrder_Cpp()
    newTree.DropNode(99999) # 不存在值操作
    newTree.LNR_MiddleOrder_Cpp()
    #%%
    # 节点搜索测试
    # 测试带有深度的节点
    print("ListValue:{0} value:{1[0]} Node:{1[1]} Path:{1[2]}".format(
        10, newTree.Search(6)))
    # 测试根节点
    print("ListValue:{0} value:{1[0]} Node:{1[1]} Path:{1[2]}".format(
        0, newTree.Search(0)))
    # 测试不存在节点
    print("ListValue:{0} value:{1[0]} Node:{1[1]} Path:{1[2]}".format(
        99999, newTree.Search(99999)))
    #%%
    # 随机数列表测试
    n = 32
    ranDataList = [random.randint(0, n // 4) for _ in range(n)]
    print(ranDataList)
    l = list(set(ranDataList))
    print(l)
    #%%
    newTree = BinaryTree() # 初始化树
    for i in ranDataList:
        newTree.addTreeNode(i)
    #%%
    # 值搜索测试
    i = ranDataList[l[len(l)//2]]
    print("ListValue:{0} value:{1[0]} Node:{1[1]} Path:{1[2]}".format(
        i, newTree.Search(i)))
    print("ListValue:{0} value:{1[0]} Node:{1[1]} Path:{1[2]}".format(
        99999, newTree.Search(99999)))

    #%%
    # 值操作测试
    newTree.LNR_MiddleOrder_Cpp()
    newTree.DropNode(l[-1]) # 删除叶子节点
    newTree.DropNode(l[1]) # 删除中间节点
    newTree.DropNode(99999) # 删除不存在节点
    newTree.LNR_MiddleOrder_Cpp()

    #%%
    # 遍历测试
    newTree.NLR_FrontOrder()
    newTree.LRN_BackOrder()
    newTree.LevelOrder_Cpp()
    newTree.NLR_FrontOrder_Cpp()
    newTree.LNR_MiddleOrder_Cpp()
#%%